996B - World Cup - CodeForces Solution

#include<bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define read(v)for(auto &i:v)cin>>i
#define pv(v)for(auto i:v)cout<<i<<" ";cout<<endl
#define pii pair<int,int>
using namespace std;
 
 
struct item{
	int c1,c2,c3,c4;
};
struct segmentTree{
	int size;
	item NEUTRAL_ELEMENT = {1,0,0,1};
	vector<item>seg;
	void init(int n){
		size = 1;
		while(size<n)size*=2;
		seg.resize(2*size,NEUTRAL_ELEMENT);
	}
	void build(vector<item>&a,int index,int lx,int rx){
		if(rx-lx==1){
			if(lx<(int)(a.size())){
				seg[index] = a[lx];
			}
			return;
		}
		int mid = (lx+rx)/2;
		build(a,2*index+1,lx,mid);
		build(a,2*index+2,mid,rx);
		seg[index] = merge(seg[2*index+1],seg[2*index+2]);
	}
	void build(vector<item>&v){
		build(v,0,0,size);
	}
	int calc(int a,int b){
		return (a*b)%mod;
	}
	item merge(item a,item b){
		item result = NEUTRAL_ELEMENT;
		result.c1 = (calc(a.c1,b.c1)+calc(a.c2,b.c3))%mod;
		result.c2 = (calc(a.c1,b.c2)+calc(a.c2,b.c4))%mod;
		result.c3 = (calc(a.c3,b.c1)+calc(a.c4,b.c3))%mod;
		result.c4 = (calc(a.c3,b.c2)+calc(a.c4,b.c4))%mod;
		return result;
	}
	// void update(int i,int v,int index,int lx,int rx){
	// 	if(rx-lx==1){
	// 		seg[index] = v;
	// 		return;
	// 	}
	// 	int mid = (lx+rx)/2;
	// 	if(i<mid)update(i,v,2*index+1,lx,mid);
	// 	else update(i,v,2*index+2,mid,rx);
	// 	seg[index] = merge(seg[2*index+1],seg[2*index+2]);
	// }
	// void update(int i,int v){
	// 	return update(i,v,0,0,size);
	// }
	item query(int l,int r,int index,int lx,int rx){
		if(lx>=l && rx<=r)return seg[index];
		if(rx<=l || lx>=r)return NEUTRAL_ELEMENT;
		int mid = (lx+rx)/2;
		item left = query(l,r,2*index+1,lx,mid);
		item right = query(l,r,2*index+2,mid,rx);
		return merge(left,right);
	}
	item query(int l,int r){
		return query(l,r,0,0,size);
	}
	void printSegment(){
		for(auto i:seg)cout<<i.c1<<" "<<i.c2<<" "<<i.c3<<" "<<i.c4<<endl;
	}
int mod;
};
// bool evenExists(vector<int>v){
// 	int n = v.size();
// 	int odd = INT_MAX;
// 	for(auto i:v){
// 		if(i%2==1)odd = min(odd,i);
// 	}
// 	for(int i=1;i<n;i++){
// 		if(v[i]%2==0){
// 			continue;
// 		}
// 		else{
// 			if(odd==INT_MAX)return false;
// 			else if(v[i]-odd>0)continue;
// 			else if(v[i]-odd<=0)return false;
// 		}
// 	}
// 	return true;
// }
int bfs(int node,vector<vector<pair<int,int>>>&adj,vector<pair<bool,int>>&vis,int prev){
	queue<pair<int,int>>q;
	vis[node].first = true;
	vis[node].second = 0;
	q.push({node,0});
	int count = 0;
	while(!q.empty()){
		int n = q.size();
		for(int i=0;i<n;i++){
			int node = q.front().first,time = q.front().second;
			if(vis[node].second==INT_MAX)vis[node].second = time;
			q.pop();
			for(auto i:adj[node]){
				int neighbourNode = i.second,neighbourTime = i.first;
				if(!vis[neighbourNode].first){
					vis[neighbourNode].first = true;
					if(neighbourTime<vis[node].second){
						vis[node].second = neighbourTime;
						count++;
					}
					q.push({neighbourNode,neighbourTime});
				}
			}
		}
	}
	return count;
}
struct producer{
	int id,profit,expense;
};


void solve()
{
	int n;
	cin>>n;
	vector<int>v(n);
	for(int i=0;i<n;i++){
		cin>>v[i];
	}
	int mini = INT_MAX;
    int gate = 0;
    for(int i=1;i<=n;i++){
    	int start = 0,end = 1e9,ans = 1e9;
    	while(start<=end){
    		ll mid = (start+end)/2;
    		if((mid*n)+i-1>=v[i-1]){
    			ans = mid;
    			end = mid-1;
    		}
    		else start = mid+1;
    	}
    	if((ans*n)+i-1<mini){
    		mini = i+(ans*n);
    		gate = i;
    	}
    }
    cout<<gate<<endl;
}
int main() {
    #ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("Error.txt","w",stderr);
	freopen("output.txt","w",stdout);
	#endif 
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t = 1;
	while(t--)
	{
		solve();
	}
	return 0; 
}